package leetcode_day._2021._202107._0110;

import java.util.*;

/**
 * @author yzh
 * @version 1.0
 * @date 2021/7/1 21:38
 * 传递信息
 * 算法：BFS 动态规划
 */
public class _01_LCP07 {
    public static void main(String[] args) {
        System.out.println(new _01_LCP07().numWays_BFS(5,
                new int[][]{{0, 2}, {2, 1}, {3, 4}, {2, 3}, {1, 4}, {2, 0}, {0, 4}}, 3));
    }

    public int numWays_BFS(int n, int[][] relation, int k) {
        Deque<Integer> queue = new LinkedList<>();
        Map<Integer, List<Integer>> map = new HashMap<>();
        for (int[] rel : relation) {
            List<Integer> list = map.getOrDefault(rel[0], new LinkedList<>());
            list.add(rel[1]);
            map.put(rel[0], list);
        }
        queue.add(0);
        for (int i = 0; i <= k - 1; i++) {
            if (queue.isEmpty()) return 0;
            int curSize = queue.size();
            for (int j = 0; j < curSize; j++) {
                int cur = queue.poll();
                if (map.containsKey(cur)) {
                    List<Integer> list = map.get(cur);
                    list.forEach(queue::offer);
                }
            }
        }
        int ans = 0;
        while (!queue.isEmpty()) if (queue.poll() == n - 1) ++ans;
        return ans;
    }

    // dp[i][j]: i 表示用的步数，j 表示位置，使用 i 步走到 j 位置的方法
    public int numWays_dynamic(int n, int[][] relation, int k) {
        int[][] dp = new int[k + 1][n];
        dp[0][0] = 1;
        for (int i = 1; i <= k; i++) {
            for (int[] r : relation) {
                int a = r[0], b = r[1];
                dp[i][b] += dp[i - 1][a];
            }
        }
        return dp[k][n - 1];
    }

}
